package LeetCode.exercise;

import java.util.*;

public class LCR114 {
    public static void main(String[] args) {
        LCR114 main = new LCR114();
        String s = main.alienOrder(new String[]{"z","x","a","zb","zx"});
        System.out.println(s);

    }
    public String alienOrder1(String[] words) {
        int[] elem = new int[26];
        Map<Character, List<Character>> edges = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < words.length; i++){
            sb.append(words[i]);
            for(int j = i + 1; j < words.length; j++){
                if(words[i].charAt(0) == words[j].charAt(0)){
                    int cur = 1;
                    while(cur < words[i].length() && cur < words[j].length()
                            && words[i].charAt(cur) == words[j].charAt(cur)){
                        cur++;
                    }
                    if(cur >= words[i].length() || cur >= words[j].length()){
                        break;
                    }
                    if(!edges.containsKey(words[i].charAt(cur))){
                        edges.put(words[i].charAt(cur), new ArrayList<>());
                    }
                    if(!edges.get(words[i].charAt(cur)).contains(words[j].charAt(cur))){
                        edges.get(words[i].charAt(cur)).add(words[j].charAt(cur));
                        elem[words[j].charAt(cur) - 'a']++;
                    }
                } else {
                    if(!edges.containsKey(words[i].charAt(0))){
                        edges.put(words[i].charAt(0), new ArrayList<>());
                    }
                    if(!edges.get(words[i].charAt(0)).contains(words[j].charAt(0))){
                        edges.get(words[i].charAt(0)).add(words[j].charAt(0));
                        elem[words[j].charAt(0) - 'a']++;
                    }
                }
            }
        }
        if(edges.isEmpty()){
            return "";
        }
        Queue<Character> q = new LinkedList<>();
        for(int i = 0; i < 26; i++){
            char c = (char) (i + 'a');
            if(elem[i] == 0 && sb.toString().contains(c + "")){
                q.offer(c);
            }
        }
        sb = new StringBuilder();
        while(!q.isEmpty()){
            char c = q.poll();
            sb.append(c);
            for (Character ch : edges.getOrDefault(c, new ArrayList<>())){
                if(--elem[ch - 'a'] == 0){
                    q.offer(ch);
                }
            }
            edges.remove(c);
        }
        return sb.toString();
    }
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> edges = new HashMap<>();
        Map<Character, Integer> in = new HashMap<>();
        boolean flag = false;
        for(String word : words){
            for(int i = 0; i < word.length(); i++){
                char ch = word.charAt(i);
                in.put(ch, 0);
            }
        }
        for(int i = 0; i < words.length; i++){
            for(int j = i + 1; j < words.length; j++){
                if(words[i].charAt(0) == words[j].charAt(0)){
                    int cur = 1;
                    while(cur < words[i].length() && cur < words[j].length()
                            && words[i].charAt(cur) == words[j].charAt(cur)){
                        cur++;
                    }
                    if(cur >= words[j].length() && cur < words[i].length()){
                        flag = true;
                        continue;
                    }
                    if(cur >= words[j].length() || cur >= words[i].length()){
                        continue;
                    }
                    if(!edges.containsKey(words[i].charAt(cur))){
                        edges.put(words[i].charAt(cur), new HashSet<>());
                    }
                    if(edges.get(words[i].charAt(cur)).add(words[j].charAt(cur))) {
                        in.put(words[j].charAt(cur), in.get(words[j].charAt(cur)) + 1);
                    }
                } else {
                    if(!edges.containsKey(words[i].charAt(0))){
                        edges.put(words[i].charAt(0), new HashSet<>());
                    }

                    if(edges.get(words[i].charAt(0)).add(words[j].charAt(0))) {
                        in.put(words[j].charAt(0), in.get(words[j].charAt(0)) + 1);
                    }
                }
            }
        }
        if(flag){
            return "";
        }
        Queue<Character> q = new LinkedList<>();
        for(Character c : in.keySet()){
            if(in.get(c) == 0){
                q.offer(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while(!q.isEmpty()){
            char c = q.poll();
            sb.append(c);
            for (Character ch : edges.getOrDefault(c, new HashSet<>())){
                in.put(ch, in.get(ch) - 1);
                if(in.get(ch) == 0){
                    q.offer(ch);
                }
            }
            edges.remove(c);
        }
        if(!edges.isEmpty()) {
            return "";
        }
        return sb.toString();
    }
}
